

import java.util.Vector;

class PriorityEvent {
    public int priority;
    public int seed;

    public PriorityEvent(int newPriority, int newInfo) {
        priority = newPriority;
        seed = newInfo;
    }

    public boolean lessThan(PriorityEvent rh) {
        return priority < rh.priority;
    }
}

class PriorityHeap {
    public PriorityHeap() {
        eventHeap = new Vector<PriorityEvent>();
    }

    // Receive a copy of the source heap so we can save it
    // This really should only be used internally, since otherwise we can't guarantee a proper incoming heap
    private PriorityHeap(Vector<PriorityEvent> source) {
        eventHeap = new Vector<PriorityEvent>(source);
    }

    // Build a new instance using our copy constructor and return it
    public PriorityHeap copy() {
        return new PriorityHeap(eventHeap);
    }

    public void enqueue(int newPriority, int newInfo) {
        // Find the beginning index for the deepest leaf's level
        int index = (int)Math.floor(Math.log((double)eventHeap.size() + 1.0)/Math.log(2.0));
        if (index > 0) {
            index = (int)(Math.pow(2.0, (double)index)) - 1;
        }

        // Find the first empty node, if there is one.
        while (index < eventHeap.size() && eventHeap.get(index) != null) {
            ++index;
        }
        
        int parent = index / 2;
        // Verify space exists and add the new event to the end of the array
        eventHeap.ensureCapacity(index + 1);
        eventHeap.add(new PriorityEvent(newPriority, newInfo));
        // While the event is higher priority than its parent in the heap (sift up)
        while (index > 0 && eventHeap.get(index).lessThan(eventHeap.get(parent))) {
            // Swap the new event into its parent
            PriorityEvent temp = eventHeap.get(parent);
            eventHeap.set(parent, eventHeap.get(index));
            // Swap the parent into the old slot
            eventHeap.set(index, temp);
            index = parent;
            parent = index / 2;
        }
    }

    private void heapify(int rootIndex) {
        int left = 2 * rootIndex + 1;
        int right = 2 * rootIndex + 2;
        int least = rootIndex;

        // Check for higher priority left leaf
        if (eventHeap.size() > left && eventHeap.get(left) != null && eventHeap.get(left).lessThan(eventHeap.get(rootIndex))) {
            least = left;
        }
        // Check for higher priority right leaf
        if (eventHeap.size() > right && eventHeap.get(right) != null && eventHeap.get(right).lessThan(eventHeap.get(least))) {
            least = right;
        }
        // Swap higher priority leaf with root if necessary
        if (least != rootIndex) {
            PriorityEvent temp = eventHeap.get(least);
            eventHeap.set(least, eventHeap.get(rootIndex));
            eventHeap.set(rootIndex, temp);
            heapify(least);
        }
    }

    public void dequeue() {
        // Clear the root element
        eventHeap.set(0, null);

        // Find the last element
        int index = eventHeap.size();
        PriorityEvent end = null;
        while (end == null && index > 0) {
            end = eventHeap.get(--index);
        }

        if (end == null) {
            // No valid element sift down, make sure the queue is empty
            eventHeap.clear();
            return;
        } else {
            // Set last element as root, clear its previous spot
            eventHeap.set(0, end);
            eventHeap.set(index, null);
        }

        // Ensure there is a full level below the deepest leaf
        // Avoids out of bounds exceptions
        // Finds the power of 2 needed to achieve currently used depth and double it for potential capacity
        eventHeap.ensureCapacity((int)Math.pow(2.0, 1.0 + Math.ceil(Math.log((double)index)/Math.log(2.0))));
        
        // Sift down the new root element (heapify)
        // "end" becomes "parent"
        heapify(0);
    }

    public boolean isEmpty() {
        return eventHeap.isEmpty();
    }

    // Returns the highest priority value, -1 otherwise
    public int currentPriority() {
        if (!isEmpty()) {
            return eventHeap.firstElement().priority;
        } else {
            return -1;
        }
    }

    // Returns the highest priority info, null otherwise
    public int currentInfo() {
        if (!isEmpty()) {
            return eventHeap.firstElement().seed;
        } else {
            return -1;
        }
    }

    public int size(){
        return eventHeap.size();
    }

    private Vector<PriorityEvent> eventHeap;
}